หลังจากวีดิชเซ็นสัญญากับสโมสรสลอบอดาอูชีตเซได้ปีครึ่ง เรดสตาร์เบลเกรด (เซอร์เวนาซเวซดา) สโมสรชื่อดังของเซอร์เบียจึงได้จับเซ็นสัญญารับเข้าสู่ระบบเยาวชน วีดิชเริ่มต้นการเป็นนักเตะชุดใหญ่ในฤดูกาลที่ถูกยืมตัวไปสปาร์ตักซูบอตีตซา (Spartak Subotica) ทีมดังใน Super Liga ของเซอร์เบียในปี 2000 หลังจากสิ้นสุดสัญญายืมตัวแล้ว วีดิชกลับมาเล่นให้กับเรดสตาร์เบลเกรดอีกครั้ง และการกลับมาครั้งนี้ทำให้เขาได้ลงเล่นอย่างสม่ำเสมอภายใต้การทำทีมของซอรัน ฟีลีพอวิช (Zoran Filipović) โดยคว้าแชมป์ Yugoslav Cup ในปี 2001–02

วีดิชได้รับปลอกแขนกัปตันทีมอย่างรวดเร็วและยังเป็นกัปตันที่ยังอายุน้อยอีกด้วย และหลังจากได้รับตำแหน่งกัปตันได้ 3 ปี เขาลงเล่นไป 67 เกม และยิงได้ถึง 12 ประตู ถือเป็นสถิติที่ดีมากสำหรับนักเตะที่อยู่ในตำแหน่งกองหลัง ชีวิตการค้าแข้งของวีดิชกับเรดสตาร์เบลเกรดสิ้นสุดลงด้วยการคว้าดับเบิลแชมป์ คือแชมป์ลีกของประเทศ (Serbia and Montenegro League) และแชมป์บอลถ้วย (Serbia and Montenegro Cup) เพราะในเดือนกรกฎาคม ค.ศ. 2004 หลังจากคว้าดับเบิลแชมป์ดังกล่าว วีดิชถูกซื้อตัวไปยังพรีเมียร์ลีกรัสเซียกับทีมสปาร์ตัคมอสโก (Spartak Moscow) โดยไม่เปิดเผยค่าตัว แต่ยังคงเป็นที่กล่าวขานว่า วีดิชคือกองหลังที่ค่าตัวแพงที่สุดในประวัติศาสตร์ของพรีเมียร์ลีกรัสเซีย